package com.dexter.year2023.charpter2_reverselinklist.level2.topic2_2两两交换链表的结点;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;
import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.printLinkedList;

/**
 * LeetCode 24. 两两交换链表中的结点
 * https://leetcode.cn/problems/swap-nodes-in-pairs/
 * <p>
 * 给你一个链表，两两交换其中相邻的结点，并返回交换后链表的头结点。你必须在不修改结点内部的值的情况下完成本题（即，只能进行结点交换）。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 * 示例 2：
 * 输入：head = []
 * 输出：[]
 * 示例 3：
 * 输入：head = [1]
 * 输出：[1]
 * <p>
 * 提示：
 * 链表中结点的数目在范围 [0, 100] 内
 * 0 <= Node.val <= 100
 *
 * @author Dexter
 */
public class SwapPairs {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4};
        Node head = initLinkedList(a);
        Node newHead = swapPairs(head);
        printLinkedList(newHead);
    }

    public static Node swapPairs(Node head) {
        Node dummy = new Node(-1);
        dummy.next = head;
        // 交换的辅助变量，每次交换都是temp node1 node2 交换完 dummy node2 node1
        Node temp = dummy;
        while (temp.next != null && temp.next.next != null) {
            Node node1 = temp.next;
            Node node2 = temp.next.next;
            // 连线
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            // temp移动
            temp = node1;
        }
        return dummy.next;
    }
}
